public class Leetcode {
}

//leetcode:1745:分割回文串IV
class Solution1 {
    public boolean checkPartitioning(String s) {
        int n = s.length();

        boolean[][] dp = new boolean[n][n];
        //查找以i位置为结尾是否为回文子串
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = i+1 < j ? dp[i+1][j-1] : true;
                }
            }
        }

        //遍历dp表判断i到j这个位置的子串是否为回文子串并且在他的前面和后面的子串是否为回文子串即0~i-1和j~n-1的子串是否为回文子串
        for(int i = 1; i < n-1; i++){
            for(int j = i; j < n-1; j++){
                //如果这三个位置都为回文子串那么就代表可以进行分割
                if(dp[0][i-1] && dp[i][j] && dp[j+1][n-1]){
                    return true;
                }
            }
        }
        return false;
    }
}

//leetcode132:分割回文串II
class Solution2 {
    public int minCut(String s) {
        int n = s.length();

        boolean[][] isPal = new boolean[n][n];
        //判断每个以i位置为结尾的地方是否为回文串
        for(int i = n-1; i >= 0; i--){
            for(int j = i; j < n; j++){
                if(s.charAt(i) == s.charAt(j)){
                    isPal[i][j] = i+1 < j ? isPal[i+1][j-1] : true;
                }
            }
        }

        //创建一个dp表，判断以i位置为结尾的能分割成回文串的最小分割次数
        int[] dp = new int[n];
        //由要求最小值，所以我们将值都初始化为Integer.MAX_VALUE
        for(int i = 0; i < n; i++) dp[i] = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            //如果0~i位置本身就是回文串，那么就不用分割，此时的最小次数就为0
            if(isPal[0][i]) dp[i] = 0;
            else{
                //如果不为回文串，就进行分割，看是否能分割成回文串
                for(int j = 1; j <= i; j++){
                    //如果分割后j~i位置为回文串
                    if(isPal[j][i]){
                        //那么我们就进行判断dp[j-1]为回文串的最小值加1后，与dp[i]位置的最小值
                        dp[i] = Math.min(dp[i] , dp[j-1] + 1);
                    }
                }
            }
        }
        //返回以n-1位置为结尾的最小分割次数
        return dp[n-1];
    }
}